单向链表反转

最近更新于 2024-05-05 14:19

情景

初始链表

反转后

测试环境

gcc 9.4.0 – 64位

编译参数:

-no-pie -std=c17 -Wall -Werror=return-type -Werror=address -Werror=sequence-point -Werror=format-security -Wextra -pedantic -Wimplicit-fallthrough -Wsequence-point -Wswitch-unreachable -Wswitch-enum -Wstringop-truncation -Wbool-compare -Wtautological-compare -Wfloat-equal -Wshadow=global -Wpointer-arith -Wpointer-compare -Wcast-align -Wcast-qual -Wwrite-strings -Wdangling-else -Wlogical-op -Wconversion -g -O0

注:

按照 C17 标准编译

禁用了编译优化

启用了调试

初始化

调用 init() 会创建一条十个节点的链表,依次存储 0~9,创建的链表名为 head(全局变量)。调用 show_node() 可以查看 head 链表中的数据。

#include <stdlib.h>
#include <stdio.h>


typedef struct ListNode
{
    int val;
    void *next;
} ListNode;


#define N   10  // 创建链表长度,默认 10 即为 0~9
ListNode *head = NULL;  // 全局链表


/**
 * @brief 添加节点
 * 
 * @param prev 上一个节点的地址,在其基础上添加新节点;传 NULL,则是创建独立的节点,如头部
 * @param val 节点要插入的值
 * @return ListNode* 返回新建节点的地址
 */
ListNode *add_node(ListNode *prev, int val)
{
    ListNode *new_node = (ListNode *) malloc(sizeof(ListNode));
    new_node->val = val;
    new_node->next = NULL;
    if (prev != NULL)
    {
        prev->next = new_node;
    }
    return new_node;
}


/**
 * @brief 显示链表内容
 */
void show_node()
{
    ListNode *ptr = head;
    while (1)
    {
        printf("%d ", ptr->val);
        ptr = ptr->next;
        if (ptr == NULL)
        {
            break;
        }
    }
    printf("\n");
}


/**
 * @brief 初始化链表
 *      共十个节点,依次存入 0~9
 * 
 */
void init()
{
    head = add_node(NULL, 0);
    ListNode *node_ptr = head;
    for (int i = 1; i < N; ++i)
    {
        node_ptr = add_node(node_ptr, i);
    }
}

实现一:迭代

    ListNode *last = NULL;
    ListNode *curr = NULL;
    ListNode *next = head;

    while (1)
    {
        last = curr;
        curr = next;
        next = next->next;
        curr->next = last;

        if (next == NULL)
        {
            head = curr;
            break;
        }
    }

然后为了测试一下效率(数据量大,结果更为稳定),将链表长度的 N 值改为了一千万,并注释了 show_node() 调用,因为在数据量比较大的情况下,调用两千万次 printf(原链表和逆序后的链表)消耗的时间着实不少,而这个并不是算法本身需要消耗的时间。

测试结果也显现出来了,调用了 show_node() 的情况下使用了 25 秒左右的时间,注释后算法本身逆序只用了三百多毫秒。

实现二:递归

大体上和迭代相差不大,只是前一种使用的循环,这个是用的函数递归。

// 调用格式:
//    head = recursion(NULL, head)
//    返回值 head 即为逆序后的头节点
ListNode *recursion(ListNode *prev, ListNode *curr);

ListNode *recursion(ListNode *prev, ListNode *curr)
{
    if (curr == NULL)
    {
        return prev;
    }
    ListNode *next = curr->next;
    curr->next = prev;
    return recursion(curr, next);
}

递归相比迭代循环代码简洁一点,但是因为进程的栈空间有限,函数递归调用,层数不能太多,我电脑上测试了下链表节点数大概在17万到18万之间有个界限,超过之后运行就会出现段错误。

而且对比一下时间,17万个节点耗时就有40毫秒左右,前面迭代一千万个节点耗时也才三百多毫秒,相比而言还是迭代效率更高,而且支持更高的节点数。

单向链表反转
Scroll to top